import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-09-12
 * Time: 0:01
 */

class Solution2 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        if(root == null) {
            return ret;
        }

        q.add(root);

        int level = 1;

        while(!q.isEmpty()) {
            int size = q.size();
            List<Integer> tmp = new ArrayList<>();


            for(int i = 0; i < size; i++) {
                TreeNode t = q.poll();
                tmp.add(t.val);

                if(t.left != null) {
                    q.add(t.left);
                }

                if(t.right != null) {
                    q.add(t.right);
                }
            }

            // 判断是否逆序
            if(level % 2 == 0) {
                Collections.reverse(tmp);
            }
            ret.add(tmp);
            level++;

        }
        return ret;
    }
}
